COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input acphdr % Section 4.6
C00003 00003	\ninepoint
C00009 00004	N. \α{Pippenger} has proved a comprehensive generalization of the results of
C00026 00005	\vfill\end
C00027 ENDMK
C⊗;
\input acphdr % Section 4.6
\open0=tmp.inx
\chpar19←1 % this will prepare a ".JST" file containing justification statistics
\runninglefthead{ARITHMETIC} % chapter title
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{TEMPORARY EXPERIMENTS FOR THE ART OF COMPUTER PROGRAMMING}
\ctrline{$\copyright$ 1980 Addison--Wesley Publishing Company, Inc.}
\vfill
\runningrighthead{EXPERIMENTS}
\section{xxx}
\eject
\setcount0 900
\ninepoint
N. \α{Pippenger} has proved a comprehensive generalization of the results of
exercises 27 and↔32. Let $L(m,p,n)$ be the maximum of $l(N)$ taken over all
$m\times p$↔matrices↔$N$ of nonnegative integers $n↓{ij}≤n$. Then $L(m,p,n)=
\min(m,p)\lg n+H/\!\lg H+{O\biglp m+p+H(\log\log H)↑{1/2}(\log H)↑{-3/2}\bigrp}$,
where $H=mp\lg(n+1)$.\xskip[{\sl SIAM J. Com\-puting \bf9} (1980), 230--250.]

{\sl Note:} Nontrivial factorizations of string
polynomials, such as the example given with this exercise, can
be found from matrix identities such as
\def\choptop#1{\vbox to 0pt{\vss\hbox{$#1$}}}
$$\left({a \atop 1}\hskip 1.5em{1\atop 0}\right)\left({\choptop b\atop 1}\hskip 1.5em{1\atop
0}\right)\left({c\atop 1}\hskip 1.5em{1\atop0}\right)\left({0\atop 1}\9
{\quad1\atop -c}\right)\left({0\atop 1}\9{\quad1\atop -b}\right)\left({0\atop
1}\9{\quad1\atop -a}\right) = \left({1\hskip 1.5em 0\atop 0\hskip 1.5em 1}\right),$$
since these identities hold even when multiplication is not commutative.
For example,
$$(abc + a + c)(1 + ba) = (ab + 1)(cba + a + c).$$
(Compare this with the ``\α{continuant polynomials}'' of Section 4.5.3.)
\vfill\end